P6288 [COCI2016-2017#1] Kralj

COCI2016-2017#1题解

因为题面不一样,作者也懒得改,所以以下兽人指侏儒,骑士指精灵

1.40分思路

​ 兽王给每个勇士选择的对手都是 1 号兽人,那么,GM所指定骑士的顺序就一定是兽人的编号,即第i个骑士对第i个兽人。现在我们只需找一种骑士的排法,使得胜场数最大。

​ 贪心的想,最强的骑士对比他弱的兽人中最强的,第二强的骑士对比他弱的兽人中最强的······直到某一位骑士无法打败任何一人。可以排序后用单调性优化。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 500000;
int n,a[ MAXN + 5 ],p[ MAXN + 5 ],v[ MAXN + 5 ];

bool cmp( const int &x , const int &y ) {
	return x > y;
}
int main( ) {
	//freopen("Kralj.in","r",stdin);
	//freopen("Kralj.out","w",stdout);
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&a[ i ]);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&p[ i ]);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&v[ i ]);
	sort( p + 1 , p + n + 1 , cmp );
	sort( v + 1 , v + n + 1 , cmp );
	
	int Ans = 0 , last = 1;
	for( int i = 1 ; i <= n ; i ++ ) {
		for( int j = last ; j <= n ; j ++ ) {
			if( v[ i ] > p[ j ] ) {
				Ans ++;
				last = j + 1;
				break;
			}
			if( j == n && v[ i ] < p[ j ] ) last = n + 1;
		}
			
		if( last == n + 1 ) break;
	}
	printf("%d",Ans);
	return 0;
}

2.100分思路

假设骑士走到aia_i后就停下,不继续向前找兽人,我们用pre[i]pre[i]表示iiii之前的节点骑士的个数。

当一个区间[i,j][i,j]内的骑士多于该区间的兽人时,可表示为:

pre[i]pre[j1]>ij+1pre[i]-pre[j-1]>i-j+1

移项得:

pre[i]i>pre[j1](j1)pre[i]-i>pre[j-1]-(j-1)

Pi=pre[i]iP_i=pre[i]-i,则Pi>Pj1P_i>P_{j-1}。由定义可得,PiP_i的意思是这个点之前的骑士与兽人的数量之差,我们设Pm=min{pi}P_m=min\{p_i\}。则一定没有骑士从 mm 走到 m+1m+1 。证明如下:

因为PmP_m最小,所以对于任意PiP_iPmPi0P_m-P_i≤0,即m之前的骑士都能找到对应的兽人。所以我们可以在 mm 处剖开链,贪心模拟。

​ 我们从 m+1m+1 开始,用 SS 表示没有坐好的骑士的集合。每次到达新的点,先加入停留在这个点上的所有骑士。现在可能有多个骑士对一个兽人,显然我们应该用实力高于这个兽人中实力最小的骑士来面对它,可以用二分求出,答案加 11。剩下的骑士向前移。如果没有骑士大于兽人的实力,就将骑士实力最弱的留下当炮灰。

注意跑环时,n+1n+1就是11,特判一下。

#include <cstdio>
#include <vector>
#include <set>
using namespace std;

const int MAXN = 500000;
int n,a[ MAXN + 5 ],p[ MAXN + 5 ],v[ MAXN + 5 ];
int pre[ MAXN + 5 ],s[ MAXN + 5 ];
int Min = 0x3f3f3f3f , Min_dex;
vector< int > vec[ MAXN + 5 ];
set< int > Set;

int solve( int x ) {
	int Ans = 0 , tot = 1;
	while( tot <= n ) {
		for( int i = 0 ; i < vec[ x ].size( ) ; i ++ )
			Set.insert( vec[ x ][ i ] );
		auto it = Set.lower_bound( p[ x ] );
		if( it == Set.end() )
			Set.erase( Set.begin() );
		else {
			Set.erase( it );
			Ans ++;
		}
		tot ++;
		x = ( x + 1 ) > n ? 1 : x + 1;
	}
	return Ans;
}
int main( ) {
	//freopen("Kralj.in","r",stdin);
	//freopen("Kralj.out","w",stdout);
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&a[ i ]);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&p[ i ]);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&v[ i ]);
	for( int i = 1 ; i <= n ; i ++ ) {
		pre[ a[ i ] ] ++;
		vec[ a[ i ] ].push_back( v[ i ] );
	}
	for( int i = 1 ; i <= n ; i ++ ) {
		pre[ i ] += pre[ i - 1 ];
		s[ i ] = pre[ i ] - i;
		if( s[ i ] < Min ) {
			Min = s[ i ];
			Min_dex = i;
		}
	}
	int cut = ( Min_dex + 1 ) > n ? 1 : ( Min_dex + 1 );
	printf("%d",solve( cut ));
	return 0;
}